Realtime System

目標：車載システムや金融システムなど、コンピュータの処理の結果が計算の正しさだけでなく計算が終わる時間にも依存するリアルタイムシステムの概念と要素技術、応用方法を習得する。

概要：実世界の時間制約下で稼働することが求められるリアルタイムシステムの基礎と応用を論じる。主な内容は、リアルタイムスケジューリング、リアルタイム同期プロトコル、マルチコア資源管理、GPU資源管理、アプリケーションなど。

授業計画

１）リアルタイムシステムの概要

２）アプリケーション（自動運転システム）

３）アプリケーション（自動運転システム）

４）アプリケーション（自動運転システム）

５）静的優先度スケジューリング

６）動的優先度スケジューリング

７）マルチコアスケジューリング

８）GPUスケジューリング

９）グラフスケジューリング

１０）同期プロトコル

１１）マルチコア同期プロトコル

１２）メモリ管理

１３）リアルタイムLinux

１４）組込みOS

１５）まとめ

第1講

リアルタイムシステムは応用が広い

加藤先生が応用分野として考えているのは自動運転

リアルタイムシステムは仮想マシンと同じくらい古い歴史がある

教科書：Hard rial-time computing systems

リアルタイムシステム：システムの正確さが論理・機能だけでなく時間にも依存するシステム

・ハードリアルタイムシステム

システムに課せられたある処理がデッドライン内に終了しな買った時、システム全体にとって致命的なダメージが生じるといった理由からデッドライン内での終了が保証されなければいけないシステム

ex.自動車のブレーキ

・ファームリアルタイムシステム

デッドラインミスが起こった時、システム全体に致命的なダメージを与えることはないが、その処理自体の価値は即座に0になる

ex.飛行機の翼

・ソフトリアルタイムシステム

デッドラインミスが起こってもシステム全体に致命的なダメージを与えることはなく、その処理自体の価値も、終了時間などにより徐々に落ちていく

例えば、飛行機が墜落したらデッドラインミスがないかシミュレーションやりまくる

ロボットがデッドラインミスをして転ぶなどということもある

どのタスクをどの瞬間に、どのプロセッサで解けばいいのかを決めるのがリアルタイムシステム

要するに数学である

飛行機や金融システムなど、必ず全ての処理を間に合わせなければいけないときに大切になる

金融のシステムのすごい

実行時間がぶれないように処理をすることもリアルタイムシステムの研究課題である

タスク間の実行時間の干渉をふせぐ

どうして防ぐかというとキャッシュをきれいにしたりする

GPUはリクエストがきたら処理をするしかできないので、CPUの段階でGPUの処理を制御する必要がある

つまりCPUのデバイスドライバがGPUを管理しなければいけない

スケジュール可能性

リアルタイムシステムに含まれるタスクのデッドラインを守れるかどうかの性質

CPUが二個以上になると難しくなるので、この講義ではCPUが１つの場合として考える

OSが１つの時はRM(Rate Monotonic)が最適だと証明されている

これはタスクの時間が短い順にスケジューリングするという方法

RMで間に合わないものはどんな優先度の付け方をしても無理だとわかる

漸化式を解くのは40年前の話で、タスク数でスケジュールを予測するという方法が最近はよく使われている

70%ぐらいまでシステムが飽和してくると、タスクがめちゃくちゃ多いとスケジュールできなくなる

システムの利用率は7割超えるようなシステムは作ってはいけないという暗黙の了解がある

タスクが増えていくと0.69ぐらいに収束していき、0.7がマジックナンバーとして知られている

第2講

リアルタイムシステム

定義：システムの正確さが論理・機能だけでなく時間にも依存するシステム

ハードリアルタイムシステム、ファームリアムタイムシステム、ソフトリアルタイムシスムが存在

2.1 Introduction

2.2 Types of task constraints

2.3 Definition of scheduling problems

2.4 Scheduling anomalies

リアルタイムシステムについては大たいOSの話

2.1 Introduction

preemption：running taskを一時停止させqueueに送る、OSの機能によって実現される

dispatching：scheduling結果に基づいてタスクをCPUに割り当てる

active task：潜在的に実行可能なタスク

ready task：待ち状態のタスク

動的リアルタイムシステムにおけるpreemption

メリット

・例外処理のタスクを既存タスクより優先的に行える

・高優先度のタスクが後から来た場合に実行できる

・プロセッサの使用効率を高くできる

デメリット

・プログラムの局所性を破壊する

・オーバーヘッドが発生する

リアルタイムシステムはOSだが、数学の問題になってくる

2.2 Types of task constraints

1 タイミング制約

2 優先順位制約

3 共有リソース制約

ロボットやAIを作ろうとすると、リアルタイムシステムの知識が必要になってくる

一番難しいのが共有リソース制約である

同期が入ると、時間が見積もれなくなる

タイミング制約

パラメータ

・Deadline

・Criticality

Lateness、Tardiness、Vaxityが、ハードリアルタイムシステムで重要になってくるパラメータたち

周期による分類

・周期タスク

・非周期タスク

・散発的タスク

優先順位制約

タスクの優先順位はDAGで表現可能

共有リソース制約

共有リソースとは複数のタスクで利用されているリソース

データの一貫性維持のため競合タスクからの同時アクセスの近σにが必要

semaphore

相互排除の実現方法の１つ

sritical section

プログラムの中の共有する資源にアクセスする部分

アポロ13は共有りそーす問題でバグが起きて、ひきかえザルをえなくなった

ロボットやAIはどんなにすごくても時間通りに動かなければ意味がないことがあるので、こういうことを考えるのは重要

2.3 Definition of Scheduling Problem

preemptive vs non-preemptive

preemptive：優先度に従って、実行中のタスクが他のタスクにプロセッサを割り当てるために実行中段されるかどうか

Static vs Dynamic

Static：システム実行時にfixedパラメータに基づいてスケジューリングが決定されるアルゴリズム

Dynamic：システム稼動中に変化するdynamicパラメータに基づいてスケジューリングが決定されるアルゴリズム

Offline vs Online

Offline：タスクがアクティブ化される前にタスクセット全体で実行される

Online：新しいタスクがシステムに入るたびに、または実行中のタスクが終了するたびに実行時のスケジューリングの決定が行われた場合のアルゴリズム

Optimal vs Heuristic

Optimal：あるコスト関数を最小にするときのアルゴリズム

Heuristic：スケジューリンgぬを決定するときにheuristic関数によって導かれるアルゴリズム

2.4 scheduling anomalies

定理

ある優先度、固定の数のプロセッサ、処理時間、順位制約がある

タスクセットマルチプロセッサで最適にスケジューリングされていることを仮定

1 プロセッサの数を増加

2 タスクの処理時間を減らす

3 順位制約を減らす

これらを行うとさらに全体の処理時間が減ると考えられるが増加する！

Anomalyがあることを知っていることは大事！

プロセッサを増やしたら、性能が良くなるとは限らない

タスクの実行時間を変えても良くなるとは限らない！

順序制約を減らしたからといって良くなるとは限らない！！

こういう例はたくさんある

ここまでは、基本的な話

Anomalyがあったり、いろんなパラメータがあるので普通には解けない問題

たくさんのアルゴリズムがあり、制約によってアルゴリズムを変えていく

これがリアルタイムシステムの研究分野

後半戦はリアルタイムアルゴリズムで、非周期的なタスクに対して考える

周期を考えるとパラメータが増えるので、いったん周期というパラメータなしで考えてみましょうということ

3.1 Introduction

3.2 Jackson’s Algorithm

3.3 Horn’s algorithm

3.4 non-preemptive algorithm

3.5 scheduling with precedence constraints

3.6 summary

3.1 Introduction

アルゴリズムの分類

3.2 Jackson’s Algorithm

EDD(Earliest Due Date)

最大遅延を最小にする

定理

独立したタスクのnこのセットが与えられているときデッドラインが短い順にタスクを実行すると、最大遅延を最小にすることに関して最適になる

背理法みたいな方法で証明する

3.3 Horn’s algorithm

Hornは単一プロセッサ上で独立したnこのタスクスケジューリングアルゴリズムを見つけた

EDFと呼ばれる

次の定理によって表される

アルゴリズムの計算量は１つのタスクにつき

・リストとしてReady Queueが実装されている→O(n)

・ヒープとしてReady Queueが実装されている→O(nlogn)

任意のarrival timeでn個の独立したタスクがあるとき全てのready tasksの中に早い絶対デッドラインを持つタスクを早期に処理するアルゴリズムはMaximum latenessを最小化する点に関して最適である

EDFはデッドラインが早いものをpreemptionしながら処理していく

EDFはあくまでpreemptiveなshcedulingに対して最適

maximum latenessを最小化する問題はNP困難になる

3.4 non-preemptive algorithm

NP困難はNP困難だが、早く処理が終わる

Spring Algorithm

ヒューリスティックにとく

今の問題を現実的な時間で求めるアルゴリズム

Partial scheduleを拡張するのに、今のスケジュールはstrongly feasibleかどうかを決める必要がある

strongly feasible とは残存するタスクを全て考慮してスケジューリングしてもスケジューリング

3.5 scheduling with precedence constraints

3.6 summary

第3講

4.1 Introduction

4.2 Timeline scheduling

4.3 Rate monotonic scheduling

4.4 Earliest Deadline First scheduling

4.5 Deadline monotonic

4.6 Earliest Deadline First scheduling

4.7 Comparison between RM and EDF

4.1 Introduction

Periodic task scheduling

制御アプリケーションがここのタイミング制約を持つ複数の同時周期タスクからなる場合、OSは各周期インスタンスを定期的に適切な頻度でアクティブかし、期限内に完了させなければならない

定期的タスクのための基本4アルゴリズム

・Timeline Scheduling

・Rate Monotonic

・Earliest Deadline First

・Deadline Monotonic

いろいろな仮定をおいてリアルタイムスケジューリングをしているが、現実ではこれらの仮定が成り立たないことが多い

すごい単純なロボットしか世に出ないのはこれが理由でもある

現実でリアルタイムスケジューリングをするのはかなり難しい

車などについても、めちゃくちゃ実験しないと世に出せない

最悪実行時間になると、キャッシュが全部当たらなかったときや、分岐予測が全て外れたときを想定しなければならない

それなので、システムの価格が高くなってしまう

仮定3,4は現実世界では厳しい仮定

そこをどうするのかが7章で議論されている

リアルタイムスケジューリングが安全であるとどういう風に表現するのかというと、パラメータで表現するしかない

パラメータとして、時間制約、順序制約、リソース制約がある

4.2 Timeline scheduling

最小公約数で区切って考えていくのが良さそう

家電はこんな感じでシンプルに実装されていることが多い

問題点として、CPU使用率が高くなってきたらデッドラインミスをしてしまう

負荷が高くならないものならOK

変更に弱いので、一回その製品を買ったら絶対変えないみたいな

利点

実装がシンプル

タスクシーケンスがカーネルではなくプログラムで起こるのでコンテストスイッチは起きず、ランタイムオーバーヘッドが非常に低い

視覚化が容易

jitterの影響を受けない

問題点

負荷が高い状態には弱い

変更に弱い

タスクシーケンスを変更

4.3 Rate monotonic scheduling

ほとんどのリアルタイムシステムはこのRate Monotonicに近いアルゴリズム

飛行機や車もこれが多いし、ロボットやAIなどの安全性を保証するためにもこのアルゴリズムに沿ってスケジューリングされるのではないかと思われる

これはシンプルである

preemptiveは優先度が高いタスクがきたらそっちに切り替えるということ

これを採用している

Rate Monotonicでスケジューラブルじゃないアルゴリズムは他のアルゴリズムでは絶対スケジュールできないことが証明されている

RMとは周期の短いタスク高い優先度を与えるアルゴリズム

RMは固定優先度割り当て

本質的にpreemptive

２つのプロセッサの利用率が83%以下ならばRMスケジューリング可能

RMの最悪の値は69%である

69%よりもCPU使用率が低かったら絶対にRMでスケジューリングできる

それより高かったらタスク数について考えるが、タスク数は変動するのでここは微妙

CPU使用率70%以上のシステムを作ると、ロボットがこけたり、ブレーキが作動しなかったりするので、70%を守ることは大切である！

第4講

4.4 Earliest Deadline First scheduling

EDFアルゴリズムは絶対デッドラインの早いものに優先度を与えるアルゴリズム

EDFとRMが分かっていればリアルタイムシステムの基本はOK

CPU利用率が0.83より小さければRMでスケジューリング可能

4.5 Deadline monotonic

DMとは、shedulability analysisの仮定をゆるくした際の静的スケジューリングである

RMとEDFのいいとこ取り

4.6 Earliest Deadline First scheduling

4.7 Comparison between RM and EDF

結論として、独立かつプリエンプティブな周期タスクは、固定、動的優先度の両方で解決することができる

固定優先度のメリット：実装が簡単

動的優先度のメリット：膨大なタスクセットを扱う場合、もしくは非常に遅いプロセッサを扱う場合に固定優先度よりも有効になる

スケジューラビリティ分析の観点からは、

双対期限がピリオドに等しい独立タスクの単純なケースでも、RMの正確な保証テストには擬似多項式の複雑さが必要だがEDFではO(n)で実行可能

デッドラインが周期以下である一般的なケースではスケジューラビリティ解析は両方のアルゴリズムで擬似多項式になる

固定優先度の下では、タスクセットの実行可能性は応答時間分析を使用してテストできるが、動的優先度割り当てではプロセッサデマンド基準を使用してテスト可能

5.1 Introduction

5.2 Background scheduling

5.4 Polling Server

5.4 Deferrable Server

5.1 Introduction

周期タスクしかないシステムはない

全章までは周期、非周期に統一されたタスクセットを扱ってきたが多くのアプリケーションはそれらが混在

周期・非周期では重要度が異なる場合がある

・周期タスク

タイミング制約が伴う

・非周期タスク

イベントドリブン型であり、アプリケーションによってリアルタイム性の要件が異なる

非リアルタイムからハードリアルタイムまで存在

これらが混在するタスクセットをハイブリッドタスクセットと呼ぶ

5.2 Background scheduling

概要

周期タスク実行下でソフトな非周期アクティビティのセットを処理する最も簡単な方法

周期タスクのインスタンスがない場合に非周期タスクをセットする

5.3 Polling Server

概要

Background scheduling の非周期タスクの平均応答時間はサーバ（可能な限り早く非周期タスクに対応することを目的とする周期タスク）を使用することで改善可能

サーバは周期的タスクと同様に期間Tsおよび計算時間Csによって特徴付けられる

一般的にサーバは周期的なタスクに使用されるのと同じアルゴリズムでスケジュールされ、一度アクティブになると容量の限度内で非周期タスクの要求を処理する

非周期タスクの要求の順序づけは周期タスクに使用される

スケジューリングアルゴリズムに依存せず、到着時間、計算時間、デッドラインまたは他の任意のパラメータによって行われる

周期Tsに等しいかんか腕PSはアクティブになり容量Csの限度内で保留中の非周期的な要求にサービスを提供する

非周期的要求が保留されていない場合、PSは次の周期の開始まで中断、非周期的サービスのために割り当てられた容量を排出し、周期的なタスクに当てる

サーバは一時停止した直後に非周期的な要求が到着した場合、容量が補充された次の期間の開始まで待機する

5.4 Deferrable Server

Deferrable ServerアルゴリズムはPolling Serverの非周期タスクの平均response timeを改善するために考案された

第5講

7.1 Introduction

7.2 The priority inversion phenomenon

7.3 Terminology and assumption

7.4 Non-preemptive Protocol

7.5 Highest locker priority protocol

7.6 Highest locker priority protocol

7.7 Priority Ceiling Protocol

7.8 STACK RESOURCE POLICY

7.9 schedulability analysis

7.10 summary

7.1 Introduction

7章では共有リソースへのアクセス方法について述べられている

排他モードで共有リソースを使用する場合においてユニプロセッサシステムで発生する可能性がある主な問題とその回避のためのリソースアクセスプロトコルを提示する

一般的なOSにおける共有リソースへの排他制御の仕組み（セマフォ）

7.2 The priority inversion phenomenon

概要

高優先度プロセスが低優先度プロセスによって待たされる現象

7.3 Terminology and assumption

仮定

用語

7.4 Non-preemptive Protocol

概要

タスクがクリティカルセクションに入るとき、そのタスクの優先度を最高にし、プリエンプションを発生させない方式

7.5 Highest locker priority protocol

リソースRkに入るタスクの優先度を最も高い優先度にあげることによってNPPを改善する

7.6 Highest locker inheritance protocol

ブロッキングを引き起こすタスクの優先順位を変更することによって無制限の優先度逆転を回避する

7.7 Priority Ceiling Protocol

PCP

priority inheritance Protocolを拡張し、優先度逆転現象、デッドロック、連鎖ブロッキングの形成を防ぐ

7.8 STACK RESOURCE POLICY

Bakerによって提案

共有リソースにアクセスするためにPriority Ceiling Protocolに３つの拡張を加えた

・複数ユニットのリソースを使用可能

・動的優先度スケジューリングのサポート

・ランタイムスタックベースのリソースの共有を可能

7.9 schedulability analysis

共有リソースが存在する場合の周期タスクセットの実現可能性を検証

独立タスクの4章で示された全てのスケジュール可能性の判定テストはブロッキング時間を含むものにも拡張可能

7.10 summary

第6講

5.5 Priority exchange

5.6 Sporadic server

5.7 Slack stealing

5.8 Non-existence of optimal servers

5.9 Performance evaluation

5.10 Summary

5.5 Priority exchange

Priority Exchangeアルゴリズムはハードな周期タスクセットに沿ったソフトな非周期リクエストセットを処理するアルゴリズム

5.6 Sporadic server

Sporadic Serverは周期タスクのutilization boundを損なわず非周期タスクの平均response timeを短くするために考案された

SSはDSのように非周期タスクのリクエストが生じるまで高優先度レベルでcapacityを保持する

5.7 Slack stealing

Slack Stealing algorithm

非周期タスクのresponse timeをPE, DS, SSよりも向上させる

サーバを立てず、Slack Stealerを利用する面が異なる

5.8 Non-existence of optimal servers

Slack stealerはもともと非周期タスクのレスポンスタイムを最小化する最適アルゴリズムとして考案された

→Slack stealerは周期タスクのschedulabilityを妨害しない範囲でできる限り早く非周期タスクを実行するものであった

しかし、非周期タスクの実行を遅らせたほうが良い場合が存在する

Tia, Kuym Shankarは周期タスクが固定優先度で動作する場合、周期タスクのschedulabilityを保証しつつ、非周期タスクのレスポンスタイムを最小化するアルゴリズムがないことを証明した

5.9 Performance evaluation

Soft aperiodic taskの平均レスポンスタイムについて本章であげたアルゴリズムとの比較を行う

5.10 Summary

第7講

6.1 Introduction

6.2 Dynamic Priority Exchange Server

6.3 Dynamic Sporadic Server

6.4 Total Bandwidth Server

6.5 Earliest Deadline Last Server

6.6 Improved Priority Exchange Server

6.7 Improving TVS

6.8 Performance evaluation

6.9 The Constant Bandwidth Server

6.10 Summary

6.1 Introduction

6章では、ソフト非周期タスクとハード周期タスクの動的優先度割り当てについてのべる

非周期要求の平均応答時間をハード周期タスクのスケジューラビリティを損なわず短縮する手法を紹介

動的優先度割り当てを固定優先度割り当てと比較した場合の特徴

より高いスケジューラビリティ

より高いプロセッサ利用率

非周期サーバのサイズが大きい

非周期タスクの応答性が高い

6.2 Dynamic Priority Exchange Server

概要

Priority Exchange serverの拡張

デッドラインベースのスケジューリングアルゴリズムで動作

保留中の非周期要求がない場合、サーバーは自身の実行時間と低優先度の周期タスクの実行時間を交換

アイドル時間以外サーバーの実行時間は周期タスクと交換される

非周期的な要求がシステムに入力されると実行時間が取り戻される

6.3 Dynamic Sporadic Server

EDFで動作するようSSを拡張

6.4 Total Bandwidth Server

SSの問題点

サーバの周期が長いと非周期要求の応答時間が悪くなる

解決策

1 サーバの周期を短くする、オーバーヘッドが増える

2 非周期要求に早めにデッドラインを割り当てる

6.5 Earliest Deadline Last Server

Earliest Deadline Last Server

非周期的な実行を進展させるために利用可能な周期タスクの余裕を利用することを基本原則としている

chettoとchettoが提示したいくつかの結果を利用してEDLサーバーの定義を行う

6.6 Improved Priority Exchange Server

前章で紹介したEDLサーバーは最適ではあるが実用性を考えるとオーバーヘッドが大きい

原因はIdle timeの計算の重さ

Improved Priority Exchangeの２つの利点

より効率的なcapacity補充方法が得られる

結果として生じるサーバは周期的ではなく常にシステム内で最高の優先順位で実行することができる

6.7 Improving TVS

6.8 Performance evaluation

6.9 The Constant Bandwidth Server

6.10 Summary

「リアルタイムスケジューリング講座」

リアルタイムで重要なのはある時刻までに結果を返すこと

ハーどリアルタイム、ファームリアルタイム、ソフトリアルタイムがある

速く処理すればいいってわけじゃない

いくらCPUが早くなっても周囲のデバイスが遅いとCPUは待たされてしまう

なぜRMアルゴリズムが注目されるのかというと、周期の長いタスクの優先度を高くしてスケジュールしたものがスケジュール可能であればRMスケジューリングでも必ずスケジュール可能である

デッドラインモノトニックスケジューリングのスケジュール可能性のための必要十分条件はRMスケジューリングの必要十分条件においてTkをDkに置き換えたモノ

EDFスケジューリング

絶対デッドラインに一番早く達するタスクに最高の優先度が与えられる

優先度が同じ場合には周期が短いタスクから実行

プライオリティインバージョン

互いに独立で優先度が異なる２つのタスクで、優先度が低いタスクの方が実行されてしまう現象

解決方法

優先度継承方式やプラオリティシーリング方式

優先度継承方式の問題点

・デッドロックが生じる可能性がある

・連続ブロッキングが生じやすい

解決方法としてプライオリティシーリング方式がある

プライオリティシーリング方式は優先度継承方式の改良版

リアルタイムスケジューリング理論とその適用事例

各種の機器や機械を制御する組み込みシステムの多くは制御対象の機器の動作する速度に合わせて動作することが要求され、リアルタイムシステムであると言える

ハードリアルタイムシステムの例として、自動車の制御システムが典型例である

ハードリアルタイムシステムを設計・開発する際は、システムが時間制約を満たすことを何らかの方法で保証することが求められている

従来はシステム設計に強い制約を課す方法や設計したシステムを徹底的にテストする方法により実現してきたが、コストがかかるので、リアルタイムスケジューリング理論が構築されてきた

RMAの概要

RMSを改良してRMAと呼ばれる体系がある

RMAは静的な優先度割付によるプリエンプティブな優先度ベーススケジューリングを行うことを前提に、最適な優先度割付方法とそのときのスケジュール可能性の解析手法を与える理論体系である

優先度ベーススケジューリングとは、最も高い優先度をもつタスクを実行し、それが実行できない状態となるまで優先度の低いタスクは一切実行しない方式

プリエンプティブは優先度の高いタスクが到着すると優先度の非口アスクがあ実行の途中であってもそれを中断して実行するタスクを切り替えることを言う

静的な優先度割付とはタスクの優先度をシステム設計時に決定する方法をいう

ほとんどのリアルタイムOSが静的な優先度割付によるプリエンプティブな優先度ベーススケジューリングを基本としていることからRMAはリアルタイムOSを用いたソフトウェアシステムに最も当てはまりやすい理論体系である

周期的には実行されないが、最小起動間隔がわかっているタスクはRMAで扱うことができる

具体的には最も頻繁に起動される条件で考える

言い換えると、最小起動間隔を周期とする周期タスクに置き換えて扱うことができる

Critical Instant

RMAの理論体系の出発点となるのがCritical Instant定理がある

あるタスクのCritical Instantとは、そのタスクが到着してから実行完了するまでの時間が最も長くなる状況

1 周期タスクのみを考える

2 各タスクの最大実行時間はあらかじめわかっている

3 各タスクの相対デッドラインが周期以下

4 タスク間に同期・通信がない

5 タスクは自ら実行を中断することはない

6 タスク切り替えなどのオーバヘッドは考えない

7 プロセッサが1つのケースのみ考える

この条件のもとで、あるタスクに対するCritical Instantはそのタスクが到着すると同時に、そのタスク以上の優先度を持つ全てのタスクが同時に到着した場合である

この定理より、Criticaal Instantから初めてタスクが実行完了するまでのスケジュールを調べることによりタスクの最大レスポンス時間を求めることができる

求めた最大レスポンス時間が相対デッドライン以下であればあいかなる状況でもタスクは時間制約を満たすことがわかる

すなわちCritical Instant定理によりタスクがいかなる場合にも時間制約を満たすことを示すために１つの状況のスケジューリングだけ調べればよいということになる

最適な優先度割付

次にタスクに対してどのように優先度を割り付けるのが最適かという問題を考える

ここでいう最適とは最適な優先度割付でスケジュール可能でなkレバどのような優先度割付でもスケジュール可能にすることはできないことを意味する

Critical Instant定理と同じ1~7の条件のもとでは相対デッドラインが短いタスクほど高い優先度を割り付けるDeadline Monotonic Schedulingが最適であることが示されている

エンジン制御システムへの応用

エンジン制御システムは制御用のコンピュータユニット、エンジンの動作状況を読み取るための多数の高精度センサと燃料噴射器や点火プラグなどのアクチュエータで構成される

RMA適用の概要

デッドラインを明確化するところから着手した

従来のRMAの拡張が必要になることがわかった

適用結果の評価

以上で述べたRMAの適用結果はタスクの最大実行時間が保証できていないという意味で100%の保証を与えるモノではない

この事例においては、あらゆる入力パターンに対してタスクを実行することが現実的でないことから困難であったが、それに加えて最近のマイクロプロセッサでは、キャッシュや分岐予測などタスクの最大実行時間の保証を困難にする機構が数多く取り入れられており、RMAを実システムに適用する上で本質的な限界となっている

この手法の適用により時間制約を余裕をもって満たせているのか、ギリギリ満たせているのかを見極めることができる

車載ネットワークへの適用

自動車内の制御用ネットワークとして広く使われているCAN(Contoroller Area Network)上のメッセージ配送にRMAを適用し、CAN上にメッセージを送信しようとしてから送信が完了するまでの最悪時間を解析する手法を提案した

CANの概要と使用方法

CANは自動車の制御システムに広く使われている

CANではネットワークに接続されたノードのクックを同期する機能はもっておらず各ノードは非同期に動作する

そのためノードを超えてのスケジューリングはできない

CANへのRMAの適用

CAN上のメッセージ配送へのRMAの適用については先行研究がある

適用結果の評価と課題

RMAの適用により実際の自動車のCANメッセージセットにおいて、時間制約が十分に満たせることがわかったことに加えて応答性を向上させるためのメッセージボックスの使い方や、オフセットの付与方法が明らかになった

残っている課題としてはゲートウェイを経由うしたメッセージ配送の最悪時間解析手法が挙げられる

現在の車載ネットワークは複数のCANバスがゲートウェイにより接続される複雑なネットワーク構成をとっており、ゲートウェイを超えたend to endでの最悪時間解析が求められている

さらなる課題として、ネットワアーク構成の最適化の問題をあげることができる

これは規模の大きい離散最適化問題となる

今後の課題と研究の方向性

これまでの経験から今後の課題を１つ挙げるならタスクの最大実行時間の評価方法をあげられる

キャッシュを持つシステムの最大実行時間解析については、国際的にも数多くの研究がなされているにもかかわらず、実用的と言える手法がないのが現状である